package P35.P34;

import org.junit.Test;

/**
 * @Author DJ同学
 * @Date 2021/2/27 11:16
 * @Version 1.0
 * @Name  在排序数组中查找元素的第一个和最后一个位置
 * @Problem https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
 * @Idea
 * 参考：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/yi-wen-dai-ni-gao-ding-er-fen-cha-zhao-j-ymwl/
 */
public class Solution {
    @Test
    public void test(){

        int[] ints = searchRange(new int[]{1}, 1);
        System.out.println("end");

    }
    public int[] searchRange(int[] nums, int target) {
        if(nums==null){
            return new int[]{-1,-1};
        }
        int begin = findBegin(nums,target);
        int end = findEnd(nums,target);
        if(begin>end){
            return new int[]{-1,-1};
        }
        return new int[]{begin,end};
    }
    private int findBegin(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while(left<=right){
            int mid = left+((right-left)>>1);
            if(nums[mid]>=target){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        //注意 等于的时候，一直右指针，所以nums[right]!=target
        return left;
    }

    private int findEnd(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;

        while(left<=right){
            int mid = left+((right-left)>>1);
            if(nums[mid]<=target){
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
        //等于的时候，一直移动左指针
        return right;

    }
}
